import java.util.*;
/**
 * 合并区间
 * 描述

给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 
0
≤
n
≤
2
×
1
0
5
0≤n≤2×10 
5
 ，区间内 的值都满足 
0
≤
v
a
l
≤
2
×
1
0
5
0≤val≤2×10 
5
 
要求：空间复杂度 
O
(
n
)
O(n)，时间复杂度 
O
(
n
l
o
g
n
)
O(nlogn)
进阶：空间复杂度 
O
(
v
a
l
)
O(val)，时间复杂度
O
(
v
a
l
)
O(val)
 */
public class 合并区间 {
    
    public static void main(String[] args) {
        

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类ArrayList 
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        // 按照区间的起始位置排序
        intervals.sort((a, b) -> a.start - b.start);
        ArrayList<Interval> result = new ArrayList<>();
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (curr.start <= prev.end) {
                // 有重叠，合并区间
                prev.end = Math.max(prev.end, curr.end);
            } else {
                // 无重叠，将上一个区间加入结果列表
                result.add(prev);
                prev = curr;
            }
        }
        // 将最后一个区间加入结果列表
        result.add(prev);
        return result;
    }

    public class Interval {
        int start;
        int end;
        public Interval(int start, int end) {
        this.start = start;
        this.end = end;
        }
     }
}
